package com.example.lcpractice.heading_offer;

public class q12 {

    public static void main(String[] args) {
        char[][] chars = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String s = "ABF";
        System.out.println(exist(chars, s));
    }

    static boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     *
     * @param board 查找目标矩阵
     * @param visited 标记是否已经查找
     * @param i 第i列
     * @param j 第j行
     * @param word 查找字符串
     * @param k 正在查找字符串第k个字符
     * @return tr
     */
    static boolean check(char[][] board, boolean[][] visited, int i, int j, String word, int k) {
        if (board[i][j] != word.charAt(k)) { //目标(i,j)字符在矩阵位置连续对齐失败
            return false;
        } else if (k == word.length() - 1) { //之前的判断确认对齐并且已经k是序号对应长度 length-1
            return true;
        }
        visited[i][j] = true; // 标记(i,j)已经找过且对齐
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  // {0, 1}代表横向右移1, {0, -1}代表横向左移1, {1, 0}代表纵向下移1, {-1, 0}代表纵向上移1
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) { // 移动后的坐标未找过
                    boolean flag = check(board, visited, newi, newj, word, k + 1); //开始递归查找下一个字符，在四个方向，是否匹配
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}
